package hot100.logos71To80;

import java.util.PriorityQueue;

/**
 * @author logos
 * date 2025/7/17 12:41
 * @version v1.0
 * @Package hot100.logos71To80
 */
public class logos74 {


    /**
     * 74. 数组中的第K个最大元素
     * https://leetcode.cn/problems/kth-largest-element-in-an-array/description/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution1 {
        public int findKthLargest(int[] nums, int k) {
            PriorityQueue<Integer> heap = new PriorityQueue<>((x,y)-> y-x);
            for (int i = 0; i < nums.length; i++) {
                heap.add(nums[i]);
            }
            for (int i = 0; i < k - 1; i++) {
                heap.poll();
            }
            return heap.peek();
        }
    }

    class Solution2 {
        public int findKthLargest(int[] nums, int k) {
            return randomSelect(nums, nums.length - k);
        }

        private static int randomSelect(int[] nums, int x) {
            int ans = 0;
            int l = 0;
            int r = nums.length - 1;
            while (l <= r) {
                int num = nums[l + (int) (Math.random() * (r - l + 1))];
                partition(nums, l, r, num);
                if (x < first) {
                    r = first - 1;
                } else if (x > last) {
                    l = last + 1;
                } else {
                    ans = nums[first];
                    break;
                }
            }
            return ans;
        }

        private static int first, last;

        private static void partition(int[] nums, int l, int r, int x) {
            first = l;
            last = r;
            int i = l;
            while (i <= last) {
                if (x == nums[i]) {
                    i++;
                } else if (nums[i] < x) {
                    swap(nums, i, first);
                    first++;
                    i++;
                } else {
                    swap(nums, i, last);
                    last--;
                }
            }
        }

        private static void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }
}
